File system services provided by the operating system of a computing system are responsible for managing the allocation of space of storage media. These file system services also provide a logical framework to the users of the computer for accessing data stored in the storage media. The logical framework usually includes a hierarchy of directory structures to locate a collection of files that contain user-named programs or data. The use of directories and files relieves the users from having to find the actual physical location of the stored information in a storage medium. Many different types of file systems are known. By way of example, popular file systems include various UNIX.TM. based file systems and the WINDOWS NT.TM. file system. One UNIX.TM. file system that incorporates the concept of "holes" (discussed below) is described in "The Design and Implementation of the 4.3BSD UNIX.TM. Operating System", S. Leffler, M. McKusick, M. Karels and J. Quarterman, chapter 7, Addison-Wesley, 1989. The WINDOWS NT.TM. file system is described in "Inside the Windows NT.TM. File System", H. Custer, Microsoft Press, 1994.
A typical file system implementation, hereafter referred to as a file system, converts from the user abstraction of a file as an array of bytes to the structure imposed by the underlying physical medium of the storage medium. Typically, magnetic disks are organized into fixed size sectors. Although the user may wish to write a single byte to a file, the disk may read or write only in multiples of sectors. Thus, in order to modify a single byte in a file, the file system must first read in the sector containing the byte to be modified, then replace the affected byte, and finally write the sector back to the disk. This operation of converting a user's random access to an array of bytes into reads and writes of disk sectors is known as block input/output or "Block I/O."
To effectively support Block I/O, a file system typically divides the array of bytes in a file into a set of fixed size clusters. A cluster may be defined as the minimum size that may be allocated for a disk. For example, if a file system's cluster size is 8192 bytes, then the first cluster allocated to a file would contain bytes 0 to 8191 of the file, and the next cluster of the file would contain bytes 8192 to 16383, etc. These clusters of a file are then stored to a disk in units of a cluster as well. The file system also divides the sectors of a disk into a set of fixed size clusters. The size of each cluster is called the cluster size. Each cluster of a disk is assigned a unique address, called a cluster number. Cluster numbers are assigned consecutively, starting from 0. If a disk has N clusters, then cluster number N-1 is the last cluster of the disk. If each cluster of a disk contains 8 sectors, then cluster number 0 corresponds to sectors numbered 0 to 7 on the disk, and cluster number 1 corresponds to sectors numbered 8 to 15 of the disk, etc. Thus, the conceptual notion of a cluster within a file is eventually written to disk at a particular cluster that has a unique cluster number.
Physical storage 10 containing clusters divided up into sectors is shown in FIG. 1. Shown is the linear physical address space of a disk (for example). The disk contains sectors of data that are organized into clusters. These clusters are shown symbolically as being linear, however, a disk controller would be responsible for allocating an individual cluster to a particular region of the disk. Shown in particular is a disk having at 12 a cluster 0 up through at 14 a cluster N-1. The disk contains N clusters. Each cluster may contain eight sectors, for example. For example, cluster 0 would correspond to sectors 0-7, cluster 1 would correspond to sectors 8-15, etc. A total of X sectors may be present on the disk. It should be appreciated that this disk as mass storage in a computer may take a variety of forms. The disk may be any type of hard disk that uses magnetic media, a floppy disk, or the like. Also the disk may be any other type of physical storage in a computer such as an optical disk, RAM, or the like.
Because a file system or disk controller in a computing system may write data to these clusters continuously or randomly, it is important to keep track of which clusters on the disk contain data, i.e. which clusters are allocated. It is also important to keep track of which clusters contain data for a given file. One method to keep track of such information is through the use of a File Allocation Table (FAT).
A particular file system implementation uses a file allocation table (FAT) to manage the allocation of clusters of a disk. These file system implementations that use a file allocation table are hereafter referred to as FAT file systems. The MSDOS, OS/2, Window 3.1 FAT and the Window 95 VFAT file systems are examples of FAT file systems that are available commercially. A FAT file system will now be described generally, and then an example is provided below with reference to FIG. 2.
Typically, a FAT file system uses one file allocation table (FAT) for each disk under its control. Each entry in a FAT for a disk is associated with (or maps to) a cluster of the disk. The first FAT entry is associated with the first cluster of the disk. The next FAT entry is associated with the next cluster of the disk, and so on. If a disk has N Clusters, then the FAT for the disk has N entries, and the last FAT entry is associated with the last cluster of the disk. In other words, it can be said that the cluster number for each cluster on the disk is used as an index into the FAT to access the FAT entry for that particular cluster on the disk.
The contents of each FAT entry for a particular cluster on the disk is itself a cluster number (representing another physical cluster on the disk) and this FAT entry is used to indicate: (1) whether the particular cluster (associated with the FAT entry) has been allocated or not (the special cluster number 0 is typically used to represent an unallocated cluster); (2) whether this cluster is the last (or only) cluster in a file (the last cluster of a file is usually represented by an invalid cluster number such as "-1" in the FAT entry for that particular cluster); and (3) the next cluster of the file. In other words, for a particular cluster of a file that is stored on disk, its cluster number (where it is stored on disk) serves as an index to the FAT, and the value stored at this FAT entry is another cluster number representing where the next cluster of the file is stored on the disk.
A file in a FAT file system having Z clusters uses Z entries in the FAT. One of the directories in a FAT file system contains a directory entry for a given file that identifies the cluster number of the first cluster of that file. And the FAT entry that corresponds to the cluster number of the first cluster of a file identifies the cluster number of the second cluster of the file, and so on. In this fashion, the FAT entries corresponding to the cluster numbers on disk for the clusters of a file form a linked list. The FAT entry for the last cluster of a file contains an invalid cluster number such as "-1", to indicate that this cluster is the last cluster of the file. The minimum space allocation unit in a FAT file system is one cluster. Since the clusters of a file may not necessarily be allocated consecutively, each read or write operation usually requires one I/O operation.
FIG. 2 shows one implementation of a file system 50 in which a file directory 51 is able to access a file allocation table 70 in order to keep track of the status of the clusters on the disk. The file directory 51 may represent a complex hierarchy of directories within a file system as will be appreciated by those of skill in the art. The file directory 51 contains a File Name field 52 and an Initial Cluster Number field 54. The File Name field lists files within the file system and the Initial Cluster Number field indicates by cluster number the first cluster on disk that is used by that file to store its data.
The structure of the file allocation table 70 will now be described. A file allocation table (FAT) may be implemented using a wide variety of data structures. It is preferable to implement a file allocation table 70 using an array in which the index of the array represents a cluster on the disk and the data at the location in the array according to the index represents the status of that cluster. In other words, the cluster number serves as an index into the FAT to access a corresponding element of the array that indicates the status of the cluster on the disk identified by its cluster number. For example, the FAT 70 is shown as having an index Cluster Number 72 that ranges from 0 to N-1. The elements of the array are a status region 74 that will indicate not only the status of a particular cluster on the disk, but also the location of the next cluster within a file. A wide variety of status information for a particular cluster may be contained within the status region 74. By way of example, it is possible to keep track of whether a cluster has been allocated or not, whether it is the last cluster within a file, etc.
For example, the FAT 70 operates to indicate the status of all of the clusters of the disk 10 shown in FIG. 1. For example, in determining the status of cluster 1, one may refer to the FAT 70. To determine the status of cluster 1, an index of 1 is used as a cluster number to gain access to the status region 76 for that cluster. As shown at 76, the status of cluster 1 is represented by a 0, indicating that this cluster is currently unallocated. A positive number of 1 or greater may indicate that the cluster is currently allocated to a particular file. Also a status of "-1" for a particular cluster may indicate that this cluster is the last cluster containing data for a particular file. It should be appreciated that other numerical conventions may be used to represent the status of a cluster.
The use of the FAT 70 with the file directory 51 will now be described. Within the file directory 51 is a File1 56 that has an Initial Cluster Number of 3. This indicates that the first cluster of data for File1 is stored in cluster 3 on the disk. This Initial Cluster Number of 3 also serves as a pointer 58 to the FAT 70. This pointer 58 points to the status region as identified by the index 3 that represents the status of cluster number 3. The status region for the index 3 is the number 2 that indicates not only that this cluster 3 has been allocated but also that the next cluster containing data for this file is cluster 2. This number 2 also serves as a pointer 78 to the status region of the FAT as indexed by cluster number 2. Contained within this status region for the cluster number 2 is the quantity N-1 that indicates not only that cluster 2 has been allocated but also that the next cluster that contains data for this file is located at cluster N-1. This quantity N-1 also serves as a pointer 80 to the status region of the FAT as indexed by the quantity N-1. Contained within this region is the quantity "-1" that indicates not only that cluster N-1 has been allocated to this file, but also that this cluster N-1 is the last cluster containing data for this file.
The File2 is represented in a similar manner. Within the file directory 51 is a File2 60 that has an Initial Cluster Number of 5. This indicates that a first cluster of data for File2 is stored in cluster 5 on the disk. This Initial Cluster Number of 5 also serves as a pointer 62 to the FAT 70. This pointer 62 points to the status region as identified by the index 5 that represents the status of cluster number 5. The status region for the index 5 is the number "-1" that indicates not only that this cluster 5 has been allocated but also that this cluster 5 is the last cluster containing data for this File2. Of course, other files within the file system may be represented in the file directory and the FAT. Files that are empty may be indicated by storing a "0" in the file directory at the Initial Cluster Number.
While most applications write data to a file sequentially, some applications write data randomly to any offset in the file. For example, an application may create a new file and then write several bytes starting at an offset T within the file. In this case, bytes between offset 0 and offset T-1 of the file will have never been written, but they are logically part of the file and are generally treated as if they all have the value zero. Also, the use of a hashing function in a database may result in clusters of a file containing nothing but zeros. In a FAT file system, clusters of a file that are completely zero are still treated as containing data; a cluster will be allocated on disk and a cluster full of zeros will be written to disk.
Since it is wasteful to store a physical cluster for a corresponding logical cluster of a file that has never been written (i.e. full of zeros), one technique employed by some file systems such as most UNIX.TM. based file systems is to avoid the actual allocation in mass storage for such a zero cluster. The file system designates a special physical cluster address, usually "0", that represents the address of a special, but non-existent, physical cluster that is full of zeros. This special physical cluster is commonly called a "hole." Prior art FAT file system implementations have typically had no such capabilities for representing holes. However, U.S. patent application entitled "File Allocation Tables with Holes" by inventors Thomas K. Wong and Peter Madany, Ser. No. 08/669,632 (allowed), filed Jun. 24, 1996, does describe a technique for representing holes within a file system that uses a file allocation table. The use of holes with a FAT file system avoids allocation of physical storage when it is not needed.
Wong, et. al, extends a FAT file system to support the use of files with "holes". It also uses this concept of "holes" within a FAT file system to support file system level compression. In this way, both compressed and expanded files in a FAT file system may coexist. Also, new disks may be configured with additional FAT entries to support compression.
Typically, a disk with N clusters in a FAT file system will have a file allocation table (FAT) that contains N entries, representing the clusters of the disk numbered 0 to N-1. Wong, et. al, provides a file allocation table extension (FAT extension) that allows for additional entries numbered from N to M-1. Thus, a total of M entries are available in the FAT and FAT extension. For example, if a disk has 10 clusters, and a FAT extension has entries, the entries in the FAT will be numbered from 0 to 9, and the FAT extension entries will be numbered from 10 to 14 for a total of M=15 entries. This FAT extension represents those clusters that are all zeros within the file system and as such provides for a way to keep track of such clusters without having to write them to disk. Thus, for a cluster that is all zeros, this cluster is not written to disk but is assigned a cluster number of N or greater. Thus, any cluster of a file with a cluster number greater than or equal to N is non-existent and is treated as if it were a cluster that is full of zeros. This representation of a zero cluster in the FAT extension is called a "hole".
It should be appreciated that clusters other than those full of zeros may be treated as "holes." For example, the convention used may be that clusters that contain all "1's" are considered as being blank and that such clusters should not be stored to disk but should be represented as a "hole". Also, a cluster that contains a uniform pattern of bits may be considered as not appropriate for writing to disk and may be represented as a "hole." Any type of data pattern represented in a cluster that need not be written to disk may be represented as a "hole."
Referring now to FIGS. 3 and 4, an embodiment of the technique described in Wong, et. al is illustrated in which an extension of a FAT is used to represent the concept of "holes" within a particular file. FIG. 3 shows at 200 a particular File3 and symbolically where its data may be stored on the disk. For example, File3 202 contains three logical clusters of data 204, 206 and 208. Relative to File3 only, these three clusters of data may be referred to as file logical clusters 0, 1 and 2. The clusters 204 and 206 each contain all zeros whereas the cluster 208 contains actual data. In previous implementations of a prior art FAT as shown in FIG. 2, cluster 204 is stored at cluster 3 on the disk, cluster 206 is stored at cluster 2 on the disk, and cluster 208 is stored at cluster N-1 on the disk. This storage of the data of File3 on the disk is shown symbolically at 210. As can be appreciated, if clusters 204 and 206 contain nothing but zeros, it is wasteful to store complete clusters full of zeros on the disk. Accordingly, an extension of a FAT may be used to represent these zero clusters and to avoid the allocation of physical clusters on disk for zero clusters. This representation 212 will be explained below with reference to FIG. 4.
FIG. 4 shows at 250 a traditional FAT 70 enhanced by a FAT extension 80 that is used in conjunction with a file directory 51. The use of this FAT extension 80 will be discussed with reference to the representation of the storage of File3 of FIG. 3. As discussed above, a FAT 70 is represented as an array in which the index of the array is a cluster number 72 that corresponds to a physical cluster on the disk, and the data stored at the element corresponding to the index represents the status of that particular cluster whose number is indicated by the index.
A FAT extension 80 may also be represented by an array that also has as an index a cluster number 84 and a status region 82. It may be possible to implement this FAT extension 80 using a wide variety of equivalent data structures. As the FAT extension 80 is an extension of the FAT 70 its index begins with cluster number N up to a cluster number M-1. As the disk of the computing system still only contains N physical clusters, the index cluster number 84 of the FAT extension 80 that ranges from N to M-1 does not correspond to physical clusters on the disk. As such, an index into the FAT extension 80 may be used to represent that a cluster of a file contains all zeros instead of allocating an actual physical cluster.
In this example, File3 has logical clusters 0 and 1 of all zeros and a logical cluster 2 that does contain data. In the prior art, these first two clusters of File3 that contain zeros are allocated to actual physical clusters on the disk. However, by using the FAT extension 80, these first two clusters of File3 that contain zeros may be represented by using entries within the FAT extension 80 instead of allocating an actual physical cluster on the disk. Shown is a file directory 51 that has within it a File3 56 that has an Initial Cluster Number of N+2. This reference N+2 serves as a pointer 58 to an entry within the FAT extension 80 indexed by the cluster number N+2. Because this initial cluster for the File3 is located at the cluster number N+2 this indicates that this initial cluster is full of zeros. At the cluster number N+2 is the quantity N+5. The quantity N+5 at this location indicates the next cluster for File3 is also represented within the FAT extension 80 at the cluster number N+5. The quantity N+5 serves as a pointer 86 to the entry located at cluster number N+5. Because this second cluster is represented at the cluster number N+5, this means that this second cluster is also completely full of zeros. Within the FAT extension 80 at the cluster number N+5 is the quantity N-1. The quantity N-1 also serves as a pointer 88 back to the FAT 70 to the entry index by the cluster number N-1. Because this third cluster of File3 is indexed by the cluster number N-1 this means that the third cluster does actually contain data and is stored at cluster N-1 on the disk. And because the FAT 70 at cluster number N-1 contains the status of "-1", this means that this third cluster is the last cluster containing data for this file.
Thus, it can be seen that physical clusters for File3 with a cluster number greater than or equal to N contain only zeros and are not represented on disk, whereas physical clusters with a cluster number of N-1 or less contain data and have allocated disk space. This representation is shown symbolically at 212 in FIG. 3. It should also be appreciated that the clusters on the physical disk that contain data for a particular file as well as the zero clusters may be found by searching from the file directory through a form of a linked list until the quantity "-1" is reached. In this fashion, a conceptual array for the File3 may be created that keeps track of where each logical cluster of File3 is represented.
However, other challenges exist for users of a FAT file system aside from the representation of holes. One major problem facing users of a FAT file system is to assign the cluster size for the FAT file system when the FAT file system is first formatted. Once set, the cluster size of a FAT file system cannot be changed easily. To change the cluster size, all the data from the disk must be first copied to a temporary storage location. Next, the disk must be reformatted with the new cluster size, and finally all of the data from the disk in temporary storage must be recopied back onto the disk. This is a time consuming and possibly error-prone procedure that most users are not willing to perform. Thus, it is important for an optimal cluster size to be chosen initially.
If the cluster size of a FAT file system is set too small, then more clusters will be needed to store the data of a file. If the file is not contiguous on disk (which is common), then each cluster must be read or written individually. Thus, small cluster size degrades the file system read/write performance since more disk I/Os are needed to read or write the data of a file. On the other hand, a cluster size for a FAT file system that is set too large may also cause problems. Since the number of clusters available on a disk depends on the cluster size, a larger cluster size will result in a smaller number of clusters available on a disk. Because each non-empty file needs at least one cluster, a larger cluster size results in a smaller number of files that can be stored on a disk. Also, if the cluster size is set too large, there may not be enough file data to fill up all the sectors in a cluster for that file. Sectors that constitute a cluster of a file that are not needed to store the data of the file cannot be used to store data from other files, resulting in many unused sectors on a disk. This is commonly known as a disk fragmentation problem.
Thus, it is desirable to create a FAT file system with a large cluster size in order to maximize I/O performance. It is also desirable to create a FAT file system with a relatively small cluster size in order to increase the number of available clusters in a FAT file system so that more files can be stored in a FAT file system. At the same time, it would be desirable to reduce the disk fragmentation in a FAT file system in order to have efficient usage of storage space.